package leetcode.greedy;

/**
 * 
 * @author 26233
 *
 *
 *给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class LeetCode45_Jump {
	
	// 在可跳的范围内判断是否还有更远的距离 O(n)
	public static int jump(int[] nums) {

		int step = 0;
		if(nums.length < 2) return step;
		int currentValue = nums[0], currentIndex = 0;
		step++;
		while(currentIndex + currentValue < nums.length - 1) {
			int tempIndex = currentIndex, tempValue = currentValue;
			for(int i = 0; i < currentValue; i++) {
				if(nums[currentIndex + i + 1] + i + 1 + currentIndex >= tempIndex + tempValue) {
					tempIndex = currentIndex + i + 1;
					tempValue = nums[currentIndex + i + 1];
				}
			}
			currentIndex = tempIndex == currentIndex ? currentIndex + nums[currentValue] : tempIndex;
			currentValue = tempIndex == currentIndex ? nums[currentIndex] : tempValue;
			step++;
		}
		
		return step;
    }
	
	
	// error
	public static int jump2(int[] nums) {

		int step = 0;
		if(nums.length < 2) return step;
		int currentValue = nums[0], currentIndex = 0;
		step++;
		while(currentIndex + currentValue < nums.length - 1) {
			int tempIndex = currentIndex + nums[currentIndex];
			for(int i = 0; i < currentValue; i++) {
				if(nums[currentIndex + i + 1] >= nums[tempIndex]) {
					tempIndex = currentIndex + i + 1;
				}
			}
			currentIndex = tempIndex;
			currentValue = nums[tempIndex];
			step++;
		}
		
		return step;
    }
	
	public static void main(String[] args) {
		int[] input = {2,3,1,1,4};
		// int[] input = {2,0,6,3,5,6,7,8,1,6,0,3,6,4,2,5,5,9};
		System.out.println(jump(input));
	}

}
